// https://leetcode.cn/problems/construct-string-from-binary-tree/?envType=problem-list-v2&envId=ezCc4wnY
/*
class Solution {
public:
    string tree2str(TreeNode* root)
    {
        if(root == nullptr) return "";

        string ret = to_string(root->val);
        if(root->left || root->right)
        {
            ret += '(';
            ret += tree2str(root->left);
            ret += ')';
        }

        if(root->right)
        {
            ret += '(';
            ret += tree2str(root->right);
            ret += ')';
        }

        return ret;
    }
};
*/


//https://leetcode.cn/problems/binary-tree-level-order-traversal/description/?envType=problem-list-v2&envId=ezCc4wnY
/*
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root)
    {
        queue<TreeNode*> que;
        int size = 0;
        vector<vector<int>> ret;
        if(root != nullptr)
        {
            que.push(root);
            size++;
        }
        while(!que.empty())
        {
            vector<int> v;
            while(size > 0)
            {
                TreeNode* l = que.front();
                if(l->left) que.push(l->left);
                if(l->right) que.push(l->right);
                v.push_back(que.front()->val);
                que.pop();
                size--;
            }
            size = que.size();
            ret.push_back(v);
        }
        return ret;
    }
};
*/


//https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/description/?envType=problem-list-v2&envId=ezCc4wnY
/*
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root)
    {
        queue<TreeNode*> que;
        int size = 0;
        vector<vector<int>> ret;
        if(root != nullptr)
        {
            que.push(root);
            size++;
        }
        while(!que.empty())
        {
            vector<int> v;
            while(size > 0)
            {
                TreeNode* l = que.front();
                if(l->left) que.push(l->left);
                if(l->right) que.push(l->right);
                v.push_back(que.front()->val);
                que.pop();
                size--;
            }
            size = que.size();
            ret.push_back(v);
        }
        reverse(ret.begin() , ret.end());
        return ret;
    }
};
*/

//https://leetcode.cn/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/description/?envType=problem-list-v2&envId=ezCc4wnY
/*
class Solution {
public:
    bool To_Stack(TreeNode* t , TreeNode* x , stack<TreeNode*>& st)
    {
        if(t == nullptr) return false;

        st.push(t);
        if(t == x) return true;

        if(To_Stack(t->left , x , st))
        {
            return true;
        }

        if(To_Stack(t->right,x , st))
        {
            return true;
        }

        st.pop();
        return false;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
    {
        if(root == p || root == q) return root;

        stack<TreeNode*> qStack;
        stack<TreeNode*> pStack;
        To_Stack(root,p,pStack);
        To_Stack(root,q,qStack);

        while(qStack.top() != pStack.top())
        {
            if(qStack.size() < pStack.size()) pStack.pop();
            else if(qStack.size() > pStack.size()) qStack.pop();
            else
            {
                qStack.pop();
                pStack.pop();
            }
        }


        return pStack.top();
    }
};
*/

//https://leetcode.cn/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/description/?envType=problem-list-v2&envId=ezCc4wnY

/*
class Solution {
public:
    void Solve(Node* cur , Node*& prev)
    {
        if(cur == nullptr) return;

        Solve(cur->left , prev);
        cur->left = prev;
        if(prev != nullptr) prev->right = cur;
        prev = cur;
        Solve(cur->right , prev);
    }
    Node* treeToDoublyList(Node* root)
    {
        if(root == nullptr) return nullptr;

        Node* prev = nullptr;
        Solve(root , prev);

        Node* head = root;
        while(head->left)
        {
            head = head->left;
        }

        head->left = prev;
        prev->right = head;
        return head;
    }
};
*/